package net.cyndeline.rldungeon.dgs.strategy.pointlessArea.algorithmModules

import net.cyndeline.rldungeon.dgs.graph.{DGSFunctionality, Room}
import scalax.collection.GraphEdge.UnDiEdge
import scalax.collection.GraphPredef.OuterEdge
import scalax.collection.immutable.Graph
import net.cyndeline.rldungeon.dgs.strategy.help.{CollapsedEdge, CollapsedNode}
import net.cyndeline.rldungeon.dgs.strategy.pointlessArea._
import com.escalatesoft.subcut.inject.{BindingModule, Injectable}
import scala.collection.mutable
import scala.reflect.runtime.universe._
import scala.reflect._
import net.cyndeline.rldungeon.dgs.strategy.pointlessArea.help._
import net.cyndeline.rldungeon.dgs.strategy.pointlessArea.algorithmModules.AlgorithmSetupResult
import net.cyndeline.rldungeon.dgs.strategy.pointlessArea.algorithms.{EdgeTrimmer, CollapsedGraphEdgeTrimmer}

/**
 * Used for injection.
 */
trait AlgorithmSetupI {
  def setup[VType <: Room[VType] : TypeTag : ClassTag, EType[X] <: UnDiEdge[X] with DGSFunctionality[X, EType] with OuterEdge[X, EType]]
           (collapsedGraph: Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner],
            regularGraph: Graph[VType, EType],
            start: CollapsedNode[VType],
            goal: CollapsedNode[VType]): AlgorithmSetupResult[VType]
}

/**
 * Contains the following results from an algorithm setup:
 *
 * @param trimmedCollapsedGraph A collapsed graph where every node of degree 1 outside the main path is pointless.
 * @param mutableStorage A map of every collapsed node to the mutable node storage it is stored in.
 * @param areaConnectionsMainPath Every node along the main path that has edges below it capable of holding responders
 *                                on the main path in the collapsed graph.
 * @param areaConnectionsOffPath Every node along the the main path that has edges below it capable of holding
 *                               responders outside the main path in the collapsed graph.
 * @param edgeMappingMainPath A mapping of nodes along the main path to the edges that appear below that node
 *                            on the main path.
 * @param edgeMappingOutsideMainPath A mapping of nodes along the main path to the edges that appear below that node
 *                                   outside the main path.
 * @tparam VType Type of vertex being represented in the collapsed graph.
 */
final case class AlgorithmSetupResult[VType <: Room[VType]]
  (trimmedCollapsedGraph: Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner],
   mutableStorage: Map[CollapsedNode[VType], NodeStorage[CollapsedNode[VType]]],
   areaConnectionsMainPath: Set[CollapsedNode[VType]],
   areaConnectionsOffPath: Set[CollapsedNode[VType]],
   edgeMappingMainPath: EdgesBelowNodes[VType],
   edgeMappingOutsideMainPath: EdgesBelowNodes[VType]) {
}

/**
 * Performs pre-algorithm preparation of data.
 */
class AlgorithmSetup(implicit val bindingModule: BindingModule) extends Injectable with AlgorithmSetupI {

  /* Removes the outermost nodes of branches in a tree graph until every node with degree 1 is either on the
   * main path, or pointless and can carry a reward and/or an activator.
   */
  private val edgeTrimmer = injectOptional[EdgeTrimmer] getOrElse { new CollapsedGraphEdgeTrimmer() }

  /* Wraps a collapse node inside a mutable storage container instead of instantiating the container inside
   * this class. Injected to make testing with mocks that take containers as parameters easier.
   */
  private val storageFactory = injectOptional[StorageFactory] getOrElse { new NodeStorageFactory() }

  /**
   *  - Checks collapsed graph for cycles
   *  - Removes meaningful nodes with degree 1 from collapsed edges
   *  - Wraps collapsed nodes in mutable storage containers
   *  - Set up a mapping of edges below nodes
   *  - Registers edges along the main path into the edge mapping
   *  - Computes which nodes along the main path are valid as area connections for pointless areas
   *
   * @param collapsedGraph A cycle-collapsed graph maintaining the entire topology of the graph it represents (i.e
   *                       shouldn't miss vertices).
   * @param regularGraph The graph being represented by the cycle-collapsed graph.
   * @param start The node containing the start room of the level.
   * @param goal The node containing the goal room of the level.
   * @return See container class description.
   */
  def setup[VType <: Room[VType] : TypeTag : ClassTag, EType[X] <: UnDiEdge[X] with DGSFunctionality[X, EType] with OuterEdge[X, EType]]
           (collapsedGraph: Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner],
            regularGraph: Graph[VType, EType],
            start: CollapsedNode[VType],
            goal: CollapsedNode[VType]): AlgorithmSetupResult[VType] = {
    if (!collapsedGraph.isAcyclic)
      throw new IllegalArgumentException("Non-acyclic cycle collapsed graph found: " + collapsedGraph)

    /* Begin by trimming away edge-nodes that aren't pointless or cannot hold rewards, to cut down on the
     * amount of edges being examined later on.
     */
    val trimmedCollapsedGraph: Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner] = edgeTrimmer.removeVertices(collapsedGraph) // Intellij type inference error

    /* A collection of mutable containers with nodes, to avoid having to synchronize multiple collections whenever
     * a node changes.
     */
    val mutableRooms: Map[CollapsedNode[VType], NodeStorage[CollapsedNode[VType]]] = getStorage(trimmedCollapsedGraph)

    val mainPath = trimmedCollapsedGraph.get(start).pathTo(trimmedCollapsedGraph.get(goal)).getOrElse(
      throw new IllegalArgumentException("No main path from " + start + " to " + goal + " found in " + trimmedCollapsedGraph)
    )

    /* Convert the main path to a list for the mapping constructor. */
    val mainPathList = (for (node <- mainPath.nodes) yield {
      val outer: CollapsedNode[VType] = node
      mutableRooms(outer)
    }).toList

    val originalToCollapsed = mapOriginalToCollapseEdgesOnMainPath(trimmedCollapsedGraph)(mainPath)

    /* Maps every node on the main path to every edge below it (between the node and the goal) that isn't
     * pointless (and thus can have responders on them).
     */
    val edgesBelowNodesOnMainPath = injectOptional[EdgesBelowNodes[VType]] getOrElse { new EdgesBelowNodesMapping(mainPathList) }
    registerEdgesOnMainPath(trimmedCollapsedGraph, regularGraph)(originalToCollapsed, mutableRooms, edgesBelowNodesOnMainPath)

    /* Same as above, but this time with every edge outside the main path. */
    val mainPathEdges = mainPath.edges.map(e => e.toOuter).toSet
    val allEdges = trimmedCollapsedGraph.edges.map(e => e.toOuter).toSet
    val pointlessEdges = allEdges diff mainPathEdges
    val graphWithNoMainPath = Graph.from(Nil, pointlessEdges)
    val edgesBelowNodesOutsideMainPath = injectOptional[EdgesBelowNodes[VType]] getOrElse { new EdgesBelowNodesMapping(mainPathList) }
    registerPointlessEdges(graphWithNoMainPath, regularGraph, edgesBelowNodesOutsideMainPath, mutableRooms, mainPathList)

    /* Find the initial set of valid area connections (nodes along the main path that has edges below them that
     * can contain responders).
     */
    val areaConnectionsMainPath = findValidAreaConnections(mainPathList, edgesBelowNodesOnMainPath)
    val areaConnectionsPointless = findValidAreaConnections(mainPathList, edgesBelowNodesOutsideMainPath)

    AlgorithmSetupResult(trimmedCollapsedGraph, mutableRooms, areaConnectionsMainPath, areaConnectionsPointless, edgesBelowNodesOnMainPath, edgesBelowNodesOutsideMainPath)
  }

  /**
   * Maps every collapsed node to a mutable storage with the node in it.
   */
  private def getStorage[VType <: Room[VType]](graph: Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner]): Map[CollapsedNode[VType], NodeStorage[CollapsedNode[VType]]] = {
    val nodes = graph.nodes.iterator
    var m = Map[CollapsedNode[VType], NodeStorage[CollapsedNode[VType]]]()

    while (nodes.hasNext) {
      val n: CollapsedNode[VType] = nodes.next()
      val storage = storageFactory.store(n)
      m += (n -> storage)
    }

    m
  }

  /**
   * Registers every edge along that main path (that can carry responders) in a mapping of edges below nodes.
   *
   * Each edge along the main path is found, and registered to the node on it closest to the goal
   * if the corresponding edge in the original graph can hold responders.
   *
   * @param collapsedGraph A cycle-collapsed graph.
   * @param originalGraph The graph that the cycle-collapsed graph is based on.
   * @param originalToCollapsed Maps vertex-pairs of original edges on the main path to their collapsed counterparts,
   *                            as well as the collapsed node on the main path that the collapsed edge should connect
   *                            to on the main path.
   * @param storage A mapping of each collapsed node to its mutable node storage.
   * @param mapping A mapping of edges being present below a node on the main path.
   */
  private def registerEdgesOnMainPath[VType <: Room[VType], EType[X] <: UnDiEdge[X] with DGSFunctionality[X, EType] with OuterEdge[X, EType]]
                                     (collapsedGraph: Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner],
                                      originalGraph: Graph[VType, EType])
                                     (originalToCollapsed: Map[(VType, VType), ((CollapsedNode[VType], CollapsedNode[VType]), CollapsedNode[VType])],
                                      storage: Map[CollapsedNode[VType], NodeStorage[CollapsedNode[VType]]],
                                      mapping: EdgesBelowNodes[VType]) {

    val originalEdgeTuples = originalToCollapsed.keys.iterator
    while(originalEdgeTuples.hasNext && !originalToCollapsed.isEmpty) {
      val t = originalEdgeTuples.next()
      val edge = findEdge(t._1, t._2, originalGraph)

      /* Checking capacity first avoids having to look through the map. */
      if (edge.remainingResponderCapacity > 0) {
        val targets = (edge._1, edge._2)
        val collapsedTargets = originalToCollapsed.get(targets)

        if (collapsedTargets.isDefined) {
          val collapsedTarget = collapsedTargets.get
          val edgeTarget: (CollapsedNode[VType], CollapsedNode[VType]) = collapsedTarget._1
          val connectingNode = collapsedTarget._2
          val edgeWithStorage = (storage(edgeTarget._1), storage(edgeTarget._2))

          mapping.registerEdges(storage(connectingNode), Set(edgeWithStorage))
        }
      }
    }
  }

  /**
   * Registers edges of a graph that aren't a part of the main path.
   * @param graph A graph containing only edges and pointless nodes with their pointless area data set.
   * @param originalGraph The graph that the collapsed graph is based upon. May contain edges and nodes from the
   *                      main path, as it is only used to look up edge instances.
   * @param mapping The edge map to register edges to.
   * @param storage Maps mutable storage to their collapsed nodes.
   * @param mainPath The main path, not found in the graph. Must contain every node referred to in any
   *                 pointless data object.
   */
  private def registerPointlessEdges[VType <: Room[VType], EType[X] <: UnDiEdge[X] with DGSFunctionality[X, EType] with OuterEdge[X, EType]]
                           (graph: Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner],
                            originalGraph: Graph[VType, EType],
                            mapping: EdgesBelowNodes[VType],
                            storage: Map[CollapsedNode[VType], NodeStorage[CollapsedNode[VType]]],
                            mainPath: List[NodeStorage[CollapsedNode[VType]]]) {

    // Maps main area connection nodes to edge tuples connected to them
    var edgeTuples = Map[NodeStorage[CollapsedNode[VType]], Set[(NodeStorage[CollapsedNode[VType]], NodeStorage[CollapsedNode[VType]])]]()

    val edges = graph.edges.toIterator
    while (edges.hasNext) {
      val e = edges.next().toOuter
      val targets: (VType, VType) = CollapsedEdge.targetsOfEdge(e)
      val originalEdge = findEdge(targets._1, targets._2, originalGraph)

      if (originalEdge.remainingResponderCapacity > 0) {
        // The main area connection in the original graph
        val originalAreaConnection = CollapsedEdge.mainAreaConnectionOfEdge(e).getOrElse {
          throw new Error("the edge " + e + " doesn't have a main area connection.")
        }

        val collapsedAreaConnection = mainPath.find(n => n.node.contains(originalAreaConnection)).getOrElse {
          throw new Error("No node on the main path " + mainPath.mkString(",") + " represents the main area connection " + originalAreaConnection)
        }

        val currentEdgeTuples = edgeTuples.getOrElse(collapsedAreaConnection, Set())
        edgeTuples += (collapsedAreaConnection -> (currentEdgeTuples + ((storage(e._1), storage(e._2)))))
      }
    }

    edgeTuples.iterator.foreach(kv => mapping.registerEdges(kv._1, kv._2))
  }

  /**
   * Maps the original targets of a set of collapsed edges to their collapsed counterparts.
   * @param collapsedGraph A cycle collapsed graph.
   * @param mainPath A path from start to goal in the collapsed graph.
   * @return A map where a tuple of type VType represents (._1, ._2) of the original edge, which is used as a key
   *         pointing to a value consisting of the a corresponding tuple of collapsed nodes, and a node representing
   *         the connection on the main path that the tuple should be mapped against in an edge-below-nodes map.
   */
  private def mapOriginalToCollapseEdgesOnMainPath[VType <: Room[VType], EType[X] <: UnDiEdge[X] with DGSFunctionality[X, EType] with OuterEdge[X, EType]]
                                        (collapsedGraph: Graph[CollapsedNode[VType], CollapsedEdge[VType]#Inner])
                                        (mainPath: collapsedGraph.Path): Map[(VType, VType), ((CollapsedNode[VType], CollapsedNode[VType]), CollapsedNode[VType])] = {
    val nodes: Iterator[collapsedGraph.type#NodeT] = mainPath.nodes.toIterator
    val edges: Iterator[collapsedGraph.type#EdgeT] = mainPath.edges.toIterator

    /* Since there's n edges and n+1 nodes, the first node will be removed so that each edge is registered with
     * the node closest to the goal (meaning that the edge is marked to appear under every node from start until
     * (but not including) the node that it is registered to).
     */
    nodes.next()

    var originalToCollapsed = Map[(VType, VType), ((CollapsedNode[VType], CollapsedNode[VType]), CollapsedNode[VType])]()

    while (nodes.hasNext && edges.hasNext) {
      val outerNode: CollapsedNode[VType] = nodes.next()
      val outerEdge: CollapsedEdge[VType]#Inner[CollapsedNode[VType]] = edges.next().toOuter

      val originalTargets: (VType, VType) = CollapsedEdge.targetsOfEdge(outerEdge)
      val collapsedTargets = (outerEdge._1, outerEdge._2)

      originalToCollapsed += (originalTargets -> ((collapsedTargets, outerNode)))
    }

    originalToCollapsed
  }

  private def findValidAreaConnections[VType <: Room[VType]](mainPath: List[NodeStorage[CollapsedNode[VType]]], edgeMap: EdgesBelowNodes[VType]): Set[CollapsedNode[VType]] = {
    val areaConnections = (for {
      mainPathNode <- mainPath
      if edgeMap.edgeAmountBelow(mainPathNode) > 0
    } yield mainPathNode.node).toSet

    areaConnections
  }

  private def findEdge[VType <: Room[VType], EType[X] <: UnDiEdge[X] with DGSFunctionality[X, EType] with OuterEdge[X, EType]]
    (a: VType, b: VType, g: Graph[VType, EType]): EType[VType] = {
    val innerA = g.get(a)
    innerA.edges.find(_.contains(b)).getOrElse {
      throw new Error("No edge found going from " + a + " to " + b)
    }.toOuter
  }
}
